# -*- coding: utf-8 -*-
# author yzs
# date 2018-12-29
#
# Searching_1
# Description
# Dilpreet wants to paint his dog- Buzo's home that has n boards with different lengths[A1, A2,..., An].
# He hired k painters for this work and each painter takes 1 unit time to paint 1 unit of the board.
# The problem is to find the minimum time to get this job done under the constraints that any painter will
# only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
# Constraints:1<=T<=100,1<=k<=30,1<=n<=50,1<=A[i]<=500
# Input
# The first line consists of a single integer T, the number of test cases. For each test case,
# the first line contains an integer k denoting the number of painters and integer n denoting the number of boards.
# Next line contains n- space separated integers denoting the size of boards.
# Output
# For each test case, the output is an integer displaying the minimum time for painting that house.
# Sample Input 1 
# 2
# 2 4
# 10 10 10 10
# 2 4
# 10 20 30 40
# Sample Output 1
# 20
# 60
# 解析：数组分段和最大值最小问题


def get_required_painters(data, n, max_pre_time):
    total = 0
    num_painters = 1
    for i in range(n):
        total += data[i]
        if total > max_pre_time:
            total = data[i]
            num_painters += 1
    return num_painters


def binary_search(data, n, k):
    low = max(data)
    high = 0
    data_len = len(data)
    for i in range(data_len):
        high += data[i]
    while low < high:
        mid = low + (high-low) // 2
        required_painters = get_required_painters(data, n, mid)
        if required_painters <= k:
            high = mid
        else:
            low = mid+1
    print(low)


t = int(input().strip())
for i in range(t):
    num = list(map(int, input().strip().split()))
    k = num[0]
    n = num[1]
    data = list(map(int, input().strip().split()))
    binary_search(data, n, k)
